照亮体育馆 Barisal Stadium
UVA10641
题目为逆时针顺序编号，这里直接将数组开两倍来处理环。（然而不知为啥开到1000也能过）
定义：
$Corners[i]$为体育馆点的坐标。
$Lights[i]$为灯的坐标及费用。
$IsShineOn_{Cur}[i]$表示第$Cur$盏灯是否能照到$i$，用于计算范围。
$Range_{Cur}$为第$Cur$盏灯的照射范围，从$Left$到$Right$，用于初始化$dp$
$dp[Left][Right]$为从第$Left$盏灯照到第$Right$盏灯的最少花费。
初始化$\pmb{IsShineOn_{Cur}[i]}$：
令$A、B$两点为体育馆的两点，$C$为体育馆的一盏灯，那么$C$要想照亮边$AB$，那么必须有$0^{\circ}< ∠BAC< 180^{\circ}$（手动转一转就知道了）
因为有：
1 | //判断第Cur盏灯能否照亮(Left,Right)的范围 |
转移方程：
经典的区间$dp$
最后答案为$min(dp[i][i+N-1]),(1\leq 1\leq N)$（双倍数组处理环的答案）
AC代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using namespace std;
constexpr static long long inf = 0x3f3f3f3f3f3f3f3f;
struct Corner {
double x, y;
}Corners[31];
struct Light {
double x, y;
long long Cost;
}Lights[1001];
struct {
int Left, Right;
}Range;
int N, M;
bool IsShineOn[1001]{ false };
long long dp[1001][1001];
bool Input() {
cin >> N;
if (!N) {
return false;
}
for (int i = 1; i <= N; ++i) {
cin >> Corners[i].x >> Corners[i].y;
}
cin >> M;
for (int i = 1; i <= M; ++i) {
cin >> Lights[i].x >> Lights[i].y >> Lights[i].Cost;
}
return true;
}
void InitIsShineOn(const int& Cur) {
memset(IsShineOn, false, sizeof(IsShineOn));
for (int i = 1; i <= N; ++i) {
int&& Position = i % N + 1;
IsShineOn[i] =
(Lights[Cur].x - Corners[i].x) * (Corners[Position].y - Corners[i].y)
>
(Corners[Position].x - Corners[i].x) * (Lights[Cur].y - Corners[i].y);
}
return;
}
void InitRange(const int& Cur) {
if (IsShineOn[1] && IsShineOn[N]) {
Range.Left = N;
Range.Right = 1;
while (IsShineOn[Range.Left]) {
--Range.Left;
}
while (IsShineOn[Range.Right]) {
++Range.Right;
}
++Range.Left;
--Range.Right;
Range.Right += N;
}
else {
Range.Left = 1;
Range.Right = N;
while (!IsShineOn[Range.Left]) {
++Range.Left;
}
while (!IsShineOn[Range.Right]) {
--Range.Right;
}
}
return;
}
bool Judgt(const int& Left, const int& Right) {
return
Range.Left - N <= Left && Range.Right - N >= Right
||
Range.Left <= Left && Range.Right >= Right
||
Range.Left + N <= Left && Range.Right + N >= Right;
}
void InitDP(const int& Cur) {
for (int Length = 0; Length < N; ++Length) {
for (int Left = 1; Left <= 2 * N - 1; ++Left) {
int&& Right = Left + Length;
if (Right > 2 * N - 1) {
break;
}
if (Judgt(Left, Right)) {
dp[Left][Right] = min(dp[Left][Right], Lights[Cur].Cost);
}
}
}
return;
}
void Compute() {
for (int Length = 0; Length < N; ++Length) {
for (int Left = 1; Left <= 2 * N - 1; ++Left) {
int&& Right = Left + Length;
if (Right > 2 * N - 1) {
break;
}
for (int k = Left; k < Right; ++k) {
if (dp[Left][k] == inf && dp[k + 1][Right] == inf) {
continue;
}
dp[Left][Right] = min(dp[Left][Right], dp[Left][k] + dp[k + 1][Right]);
}
}
}
}
long long DP() {
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= M; ++i) {
InitIsShineOn(i);
InitRange(i);
InitDP(i);
}
Compute();
long long Ans = inf;
for (int i = 1; i <= N; ++i) {
Ans = min(Ans, dp[i][i + N - 1]);
}
return Ans;
}
int main() {
while (Input()) {
long long&& Ans = DP();
if (Ans == inf) {
puts("Impossible.");
}
else {
cout << Ans << endl;
}
}
return 0;
}
